public class Solution230 {
    public int kthSmallest(TreeNode root, int k) {
        if (root == null) {
            return 0;
        }
        int l = getCount(root.left);
        if (l == k - 1) {
            return root.val;
        } else if (l < k - 1) {
            return kthSmallest(root.right, k - l - 1);
        } else {
            return kthSmallest(root.left, k);
        }
    }

    int getCount(TreeNode root) {
        if (root == null) {
            return 0;
        }
        return getCount(root.left) + getCount(root.right) + 1;
    }
}
